﻿/*
题目：最小体力消耗路径

你准备参加一场远足活动。给你一个二维 rows x columns 的地图 heights ，其中 heights[row][col] 表示格子 (row, col) 的高度。一开始你在最左上角的格子 (0, 0) ，且你希望去最右下角的格子 (rows-1, columns-1) （注意下标从 0 开始编号）。你每次可以往 上，下，左，右 四个方向之一移动，你想要找到耗费 体力 最小的一条路径。

一条路径耗费的 体力值 是路径上相邻格子之间 高度差绝对值 的 最大值 决定的。

请你返回从左上角走到右下角的最小 体力消耗值 。

https://leetcode.cn/problems/path-with-minimum-effort/description/
*/

#include <iostream>
#include <string>
#include <vector>
#include <list>
#include "TreeNode.hpp"
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <functional>

using namespace std;

class UnionFind {
public:
    UnionFind(int n) {
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
    }

    int get_parent(int x) {
        return x == parent[x] ? x : parent[x] = get_parent(parent[x]);
    }

    void joint(int x, int y) {
        if (x == y) return;
        int i = get_parent(x);
        int j = get_parent(y);

        parent[j] = i;
    }

    bool connected(int x, int y) {
        return get_parent(x) == get_parent(y);
    }

private:
    vector<int> parent;
};

class Solution {
public:
    int n, m;

    // 并查集，将所有权值从小到大排序，到加到一定程序的时候，(0, 0) 和 (n - 1, m - 1) 互通的时候
    int minimumEffortPath(vector<vector<int>>& h) {
        n = h.size(), m = h[0].size();

        UnionFind uf(n * m);
        vector<vector<int>> edges;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i < n - 1)
                    edges.push_back({ i, j, i + 1, j, abs(h[i][j] - h[i + 1][j]) });
                if (j < m - 1)
                    edges.push_back({ i, j, i, j + 1, abs(h[i][j] - h[i][j + 1]) });
            }
        }

        ::sort(edges.begin(), edges.end(), [](const auto& x, const auto& y) {
            return x[4] < y[4];
            });

        int start_point = 0;
        int end_point = (n - 1) * m + (m - 1);
        for (int i = 0; i < edges.size(); i++) {
            auto& edge = edges[i];
            int p1 = edge[0] * m + edge[1];
            int p2 = edge[2] * m + edge[3];
            int w = edge[4];
            uf.joint(p1, p2);

            if (uf.connected(start_point, end_point))   return w;
        }

        return 0;
    }
};
